package code.commonAlgorithm;

/**
 * @author cuihaoran
 * @date 2025/1/16
 */
public class DictionaryTree {
    DictionaryTreeNode root;

    public DictionaryTree() {
        root = new DictionaryTreeNode();
    }

    private void addWord(String word) {
        char[] wordChars = word.toCharArray();
        DictionaryTreeNode node = root;
        for (char wordChar : wordChars) {
            int val = wordChar - 'a';
            if (node.chars[val] == null) {
                node.chars[val] = new DictionaryTreeNode();
            }
            node = node.chars[val];
        }
        node.isWord = true;
    }

    private boolean isWord(String word) {
        char[] wordChars = word.toCharArray();
        DictionaryTreeNode node = root;
        for (char wordChar : wordChars) {
            int val = wordChar - 'a';
            if (node.chars[val] == null) {
                return false;
            }
            node = node.chars[val];
        }
        return node.isWord;
    }

    private boolean isWordDFS(String word) {
        return isWordDFS_(word, 0, root);
    }

    private boolean isWordDFS_(String word, int index, DictionaryTreeNode root) {
        int wordLen = word.length();
        if (index == wordLen)
            return root.isWord;
        char c = word.charAt(index);
        int val = c - 'a';
        if (root.chars[val] == null)
            return false;
        return isWordDFS_(word, index + 1, root.chars[val]);
    }
}

class DictionaryTreeNode {
    DictionaryTreeNode[] chars;
    boolean isWord;

    public DictionaryTreeNode() {
        chars = new DictionaryTreeNode[26];
        isWord = false;
    }
}